home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 09 - 1993 / 09.03 Mar 93 / Programmers' Challenge / CityPath.c
Encoding:
Text File  |  1993-01-17  |  6.7 KB  |  241 lines  |  [TEXT/KAHL]
  1. //******************************************
  2. //    Travelling Salesman by Ronald M. Nepsund
  3.  
  4. #include <math.h>
  5.  
  6. #define    fracBase    0x20000000
  7.  
  8. //There are two 32 by 20 arrays of longs
  9. //which together give the distance betwean
  10. //any two cities.
  11. //Instead of using Array[i,j] to access
  12. //the array Array[(i<<5)+j] is used
  13. //and two longs are needed to accurately
  14. //measure the distance betwean cities
  15. //so two arrays of longs are used.
  16. //gDistanceFrac is used to hold the
  17. //fractional part of distance in 1/0x20000000
  18. //of a unit.
  19. long    gDistanceInt[640],
  20.         gDistanceFrac[640];
  21. //these are used to represent a path betwean the cities.
  22. Byte    gNextCity[20],gOptPath[20];
  23. //how long is the currently selected best path so far.
  24. long    gBestPathLength,gFracBestPathLength;
  25.  
  26. unsigned    short    gNumCities;
  27. unsigned    short    gStartCityIndex;
  28.  
  29. //precalculated square root for zero to 25
  30. long    qSquTableInt[]    =
  31.         {0,1,1,1,2,2,2,2,2,3,3,3,3,3,3,3,
  32.          4,4,4,4,4,4,4,4,4,
  33.          5,5,5,5,5,5,5,5,5,5,5};
  34. //precalculated square root - fractional part
  35. //in 1/0x20000000 of a whole unit
  36. long    qSquTableFrac[]    =
  37.         {0,0,222379212,393016784,0,126738030,
  38.         241317968,346685095,444758425,0,
  39.         87122155,169986639,249162657,
  40.         325102865,398174277,468679365,0,
  41.         66091829,130266726,192682403,
  42.         253476060,312767944,370664138,
  43.         427258795,482635936,0 };
  44.  
  45. void DoPath(short cityIndex, long    InttPathLength, long    fracPathLength);
  46.  
  47. //The recursive routien that actually finds
  48. //the shortest path.
  49. void    DoPath(register    short cityIndex,
  50.                 long    InttPathLength,
  51.                 long    fracPathLength)
  52. {
  53.     register    short    i;
  54.     Boolean    lastCity;
  55.     long    offset;
  56.     
  57.     if (fracPathLength > fracBase)    {
  58.         //the fractional value variable has
  59.         //exceeded the value of one whole
  60.         //unit
  61.         InttPathLength += 1;
  62.         fracPathLength -= fracBase;
  63.     }
  64.     
  65.     //Has the path has become longer than the
  66.     //shortest path we have already found?
  67.     if (InttPathLength > gBestPathLength ||
  68.         ((InttPathLength == gBestPathLength) &&
  69.          (fracPathLength >= gFracBestPathLength)))
  70.           return;
  71.     
  72.     //lastCity is used to tell if all the
  73.     //cities have been visited
  74.     lastCity = TRUE;
  75.     //for each city
  76.     for(i = 0; i<gNumCities; i++)
  77.         //if not to same city or already
  78.         //visited city
  79.         if ( i != cityIndex &&
  80.              gNextCity[i] == 0xFF)    {
  81.             //not at the end of the path
  82.             lastCity = FALSE;
  83.             //path from city 'cityIndex' to 'i'
  84.             gNextCity[cityIndex] = i;
  85.             //offset into distance arrays
  86.             offset = (cityIndex << 5) + i;
  87.             //go to next city adding the
  88.             //distance to that city to the
  89.             //path length
  90.             DoPath(i,
  91.              InttPathLength+gDistanceInt[offset],
  92.              fracPathLength+gDistanceFrac[offset]);
  93.         }    //end if and for
  94.     
  95.     // if this is the last city in the chain and
  96.     // is a shorter path than the previous best
  97.     if ((lastCity) &&
  98.         ((InttPathLength < gBestPathLength) ||
  99.          ((InttPathLength == gBestPathLength) &&
  100.           (fracPathLength < gFracBestPathLength))
  101.           ) )    {
  102.         // make this the current best path
  103.         register    long    *LPnt1,*LPnt2;
  104.         //this is the current shortest path length now
  105.         gBestPathLength        = InttPathLength;
  106.         gFracBestPathLength = fracPathLength;
  107.         //copy path to 'optPath'
  108.         LPnt1 = (long *)&gNextCity;
  109.         LPnt2 = (long *)&gOptPath;
  110.         for (i= ((3+gNumCities) >> 2); i>0; i--)
  111.             *LPnt2++ = *LPnt1++;
  112.     }    else    
  113.         //this city is no longer connected to the next city
  114.         gNextCity[cityIndex] = 0xFF;
  115. }
  116.  
  117.  
  118. void InitDistances(unsigned short numCities, Point    *citiesPtr);
  119.  
  120. //initialize two arrays which will give the
  121. //distance betwean any two cities.
  122. void    InitDistances(
  123.             unsigned short numCities,
  124.             Point    *citiesPtr)
  125. {
  126.     short    i,j,offset;
  127.     register    long    *LPntl1,*LPntF1,
  128.                         *LPntI2,*LPntF2;
  129.     long    dist;
  130.     short    deltax,deltay;
  131.     double     X;
  132.     
  133.  
  134. //The distance from city i to j is the same
  135. //as from city j to i.
  136. //Use pointers into the arrays
  137. //We will add a constant to the pointers to
  138. //step through the array
  139. //instead of doing a multiplication to find
  140. //the wanted entries in the array
  141.  
  142.     //how far is it betwean any two cities
  143.     for (i=0; i<numCities; i++)    {
  144.         LPntl1 = gDistanceInt  + i;
  145.         LPntF1 = gDistanceFrac + i;
  146.         offset = i << 5;
  147.         LPntI2 = gDistanceInt  + offset;
  148.         LPntF2 = gDistanceFrac + offset;
  149.         for (j=0; j<=i; j++)
  150.             if (i==j)    {
  151.                 //both pointers are pointing
  152.                 //to the same locations in the array
  153.                 //distance to the same city is zero
  154.                 *LPntI2++ = 0;
  155.                 *LPntl1 = 0;    LPntl1 += 32;
  156.                 *LPntF2++;
  157.                 LPntF1 += 32;
  158.             }    else    {
  159.                 //calculate horizontal and vertical distance betwean city 'i' and 'j'
  160.                 deltax = citiesPtr[i].h-citiesPtr[j].h;
  161.                 deltay = citiesPtr[i].v-citiesPtr[j].v;
  162.                 //The distance betwean the cities is
  163.                 // squareRoot( deltax*deltax + deltay*deltay)
  164.                 //Where you can, do multiplications using shorts
  165.                 //instead of long's - They are faster.
  166.                 if (-255< deltax && deltax<256)
  167.                         if (-255< deltay && deltay<256)
  168.                             dist = ((long)(deltax*deltax) + (long)(deltay*deltay));
  169.                         else
  170.                             dist = ((long)(deltax*deltax) + (long)deltay*deltay);
  171.                     else
  172.                         if (-255< deltay && deltay<256)
  173.                             dist = ((long)deltax*deltax + (long)(deltay*deltay));
  174.                         else
  175.                             dist = ((long)deltax*deltax + (long)deltay*deltay);
  176.  
  177.                         
  178.                 //do squareRoot
  179.                 if (dist <= 25)    {
  180.                     //use sqrt lookup tables for 0 to 25
  181.                     *LPntI2++  = *LPntl1 = qSquTableInt[dist];
  182.                      LPntl1 += 32;
  183.                     *LPntF2++  = *LPntF1 = qSquTableFrac[dist];
  184.                      LPntF1 += 32;
  185.                 }    else    {
  186.                     X = sqrt(dist);
  187.                     //gDistanceInt[(i << 5) + j] = X;
  188.                     //gDistanceInt[(j << 5) + i] = X;
  189.                     dist = X;    // integer part of distance betwean points
  190.                     *LPntl1 = *LPntI2++  = dist;
  191.                     LPntl1 += 32;
  192.                     
  193.                     //gDistanceFrac[i << 5 + j] = (X - dist) * $20000000;
  194.                     //gDistanceFrac[j << 5 + i] = (X - dist) * $20000000;
  195.                     dist = (X - dist) * fracBase; // fractional part
  196.                     *LPntF2++  = *LPntF1 = dist;
  197.                      LPntF1 += 32;
  198.                 }
  199.             }
  200.     }
  201. }
  202.  
  203. void OptimalPath(unsigned short numCities,unsigned short startCityIndex,
  204.     Point *citiesPtr,Point *optimalPathPtr);
  205.  
  206. void OptimalPath(numCities,startCityIndex,citiesPtr,optimalPathPtr)
  207. unsigned short numCities;
  208. unsigned short startCityIndex;
  209. Point    *citiesPtr;
  210. Point    *optimalPathPtr;
  211. {
  212.     register short    i,j;
  213.     long    time,index;
  214.     double    X;
  215.     
  216.     //generates the tables for the distances betwean any two cities.
  217.     //This routien takes up most of the time.
  218.     InitDistances(numCities,citiesPtr);
  219.     
  220.     //OxFF means that there is no path from
  221.     //this city to another
  222.     for (i=0; i<numCities; i++)
  223.         gNextCity[i] = 0xFF;    //no paths betwean cities
  224.  
  225.     gNumCities = numCities;
  226.     gStartCityIndex = startCityIndex;
  227.     //any path done by DoPath will be shorter than this
  228.     gBestPathLength = 0x7FFFFFFF;
  229.     gFracBestPathLength = 0;
  230.  
  231.     DoPath(startCityIndex,0,0);  //find the best path
  232.     
  233.     //put the best path into the form
  234.     //desired for 'optimalPath'
  235.     j=startCityIndex;
  236.     for(i=0; i<numCities; i++)    {
  237.         optimalPathPtr[i] = citiesPtr[j];
  238.         j = gOptPath[j];
  239.     }
  240. }
  241.